#include <stdio.h>
#include <assert.h>
#include <new>
#include <algorithm>

struct Node {
	enum ColorType {
		TYPE_RED = 1,
		TYPE_BLACK = 2
	};

	Node *parent;
	Node *left;
	Node *right;
	int  value;
	ColorType color;
};

class RBTree {

public:

	RBTree() : valid_(false) {
	}

	bool Init() {
		nodes_ = new (std::nothrow) Node[MAX_NUM_NODES];
		if (nodes_ == NULL) {
			valid_ = false;
			return false;
		}
		nodes_[0].parent = nodes_[0].left = nodes_[0].right = NULL;
		num_nodes_ = 1;
		return true;
	}

	void Reset() {
		nodes_[0].parent = nodes_[0].left = nodes_[0].right = NULL;
		num_nodes_ = 1;
	}

	bool Insert(int val) {
		if (num_nodes_ == MAX_NUM_NODES) {
			return false;
		}
		return DoInsert(nodes_, &(nodes_[0].left), nodes_[0].left, val);
	}

	bool EnsureOrdered() const {
		if (nodes_[0].left == NULL) {
			return true;
		}
		bool inited = false;
		int prev = 0;
		return Check(nodes_[0].left, inited, prev);
	}

	bool EnsureRedBlackTree() const {
		if (nodes_[0].left && nodes_[0].left->color == Node::TYPE_RED) {
			//root node must be black
			return false;
		}
		return CheckRedBlack(nodes_[0].left) >= 0;
	}

	class Iterator {
		
	};

private:

	int CheckRedBlack(const Node *node) const {
		if (node == NULL) {
			return 0;
		}
		if (node->color == Node::TYPE_RED) {
			if ((node->left && node->left->color == Node::TYPE_RED) ||
				(node->right && node->right->color == Node::TYPE_RED)) {
				return -1;
			}
		}
		int r1 = CheckRedBlack(node->left);
		int r2 = CheckRedBlack(node->right);
		if (r1 != r2 || r1 < 0 || r2 < 0) {
			return -1;
		}
		return r1 + (node->color == Node::TYPE_RED ? 0 : 1);
	}

	bool Check(const Node *root, bool inited, int prev) const {
		if (root->left) {
			if (!Check(root->left, inited, prev)) {
				return false;
			}
		}
		
		if (inited && prev > root->value) {
			return false;
		}
		inited = true;
		prev = root->value;

		if (root->right) {
			return Check(root->right, inited, prev);
		}
		return true;
	}

	bool DoInsert(Node *parent, Node **childptr, Node *subtree, int val) {
		if (subtree == NULL) {
			Node &node = nodes_[num_nodes_++];
			node.parent = parent;
			node.left = node.right = NULL;
			node.value = val;
			node.color = Node::TYPE_RED;
			*childptr = &node;
			Adjust(&node);
			return true;
		}
		if (subtree->value > val) {
			return DoInsert(subtree, &(subtree->left), subtree->left, val);
		}
		return DoInsert(subtree, &(subtree->right), subtree->right, val);
	}

	void LeftRotate(Node *node) {
		Node *p = node->right;
		node->right = p->left;
		if (node->right) {
			node->right->parent = node;
		}
		p->left = node;
		p->parent = node->parent;
		node->parent = p;
		if (p->parent) {
			if (p->parent->left == node) {
				p->parent->left = p;
			}
			else {
				p->parent->right = p;
			}
		}
		return;
	}

	void RightRotate(Node *node) {
		Node *p = node->left;
		node->left = p->right;
		if (node->left) {
			node->left->parent = node;
		}
		p->right = node;
		p->parent = node->parent;
		node->parent = p;
		if (p->parent) {
			if (p->parent->left == node) {
				p->parent->left = p;
			}
			else {
				p->parent->right = p;
			}
		}
		return;
	}

	void Adjust(Node *node) {
		Node *p = node->parent;
		if (p == nodes_) {//root node
			node->color = Node::TYPE_BLACK;
			return;
		}
		if (p->color == Node::TYPE_BLACK) {
			return;
		}
		Node *g = p->parent;
		Node *u = p == g->left ? g->right : g->left;
		if (u && u->color == Node::TYPE_RED) {
			u->color = Node::TYPE_BLACK;
			p->color = Node::TYPE_BLACK;
			g->color = Node::TYPE_RED;
			Adjust(g);
			return;
		}
		if (p == g->left) {
			if (node == p->right) {
				LeftRotate(p);
				p = node;
			}
			p->color = Node::TYPE_BLACK;
			g->color = Node::TYPE_RED;
			RightRotate(g);
		}
		else {
			if (node == p->left) {
				RightRotate(p);
				p = node;
			}
			p->color = Node::TYPE_BLACK;
			g->color = Node::TYPE_RED;
			LeftRotate(g);
		}
		return;
	}

	enum {

		MAX_NUM_NODES = 1 << 20
	};

	bool valid_;

	Node *root_;

	Node *nodes_;

	int num_nodes_;

};

int main(int argc, char *argv[]) {

	RBTree tree;
	bool ret = tree.Init();
	assert(ret);

	int num_elems = 0;
	int c = 0;
	while (scanf("%d", &num_elems) == 1) {
		tree.Reset();
		int elem;
		for (int i = 0; i < num_elems; ++i) {
			scanf("%d", &elem);
			tree.Insert(elem);
		}
		assert(tree.EnsureOrdered());
		assert(tree.EnsureRedBlackTree());
		printf("tree %d OK.\n", c++);
	}
	return 0;
}
